package com.example.sword;

public class Test39 {

    public static void main(String[] args) {
        System.out.println("haha");
    }

    public class TreeNode {
        int val;
        TreeNode left = null;
        TreeNode right = null;

        TreeNode(int val) {
            this.val = val;
        }


    }


    /**
     *
     * 输入一棵二叉树，判断该二叉树是否是平衡二叉树。
     *
     * 在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树
     *
     * 平衡二叉树
     * 是一棵空树，或者是具有以下性质：
     * 它的左右两个子树的深度差的绝对值不超过1；
     * 它的左右两个子树也分别是平衡二叉树。
     *
     */

    public boolean IsBalanced_Solution(TreeNode root) {

        if (root==null)return true;
        if (getDepth(root)==-1)return false;
        return true;
    }

    public int getDepth(TreeNode root){

        if (root==null)return 0;
        int left = getDepth(root.left);
        int right = getDepth(root.right);
        //左子树或右子树不为平衡二叉树直接返回
        if (left==-1||right==-1)return -1;
        //对各级子树做判断
        if (Math.abs(right-left)>1)return -1;

        return Math.max(left,right)+1;
    }


}
